from typing import List
# 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
#
# candidates 中的每个数字在每个组合中只能使用 一次 。

####技巧就是 start要先排序 再去剪纸 这样不需要去重


class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # 对候选数字列表进行排序，方便剪枝
        candidates.sort()

        # 初始化结果列表
        res = []

        # 定义深度优先搜索函数
        def dfs(start, target, path):
            # 如果目标数为0，说明找到了一组满足条件的数字组合
            if target == 0:
                res.append(path.copy())
                return
            # 如果目标数小于0，说明当前组合不满足条件，回溯
            if target < 0:
                return

            # 遍历候选数字列表，尝试所有可能的数字组合
            for i in range(start, len(candidates)):
                # 剪枝：如果当前数字大于目标数，后续数字也一定大于目标数，直接结束循环
                if candidates[i] > target:
                    return
                # 去重：跳过相同的数字
                if i > start and candidates[i] == candidates[i - 1]:   #太精髓了
                    continue
                # 将当前数字添加到组合中
                path.append(candidates[i])
                # 递归调用深度优先搜索函数，更新目标数和组合
                dfs(i + 1, target - candidates[i], path)# 加1 是保证不选到自己
                # 回溯，将当前数字从组合中移除，尝试下一个数字
                path.pop()

        # 从第一个候选数字开始搜索
        dfs(0, target, [])
        # 返回所有满足条件的数字组合
        return res




lll = Solution()
print(lll.combinationSum2([10,1,2,7,6,1,1,1,1,1,1,5], 8))
# 1 1 2 5 6 7 10
#
# 1 1 6
# 1 2 5
# 17
# 123
# 17
# 26





